With increasing development of the processor, the demand on the operating efficiency of the processor is gradually increased. Take an out-of-order processor for example. By using a register-renaming technology, the data-dependence problem is solved. As such, the processor could execute the instruction without the need of following the sequence of the source codes.
FIG. 1A schematically illustrates a process of executing a program without using a register-renaming technology according to the prior art. FIG. 1B schematically illustrates a process of executing a program by using a register-renaming technology according to the prior art.
The actions of executing the program by a processor could be understood from the pseudo codes shown in FIG. 1A. In the first step, a memory read action is implemented to temporarily store the data of the memory address [1024] into the R1 register. In the step 2, the data stored in the R1 register is added by 2, and then the result is stored back to the R1 register. In the step 3, a memory write action is implemented to write the data that is stored in the R1 register into the memory address [1032]. In the fourth step, a memory read action is implemented to temporarily store the data of the memory address [2048] into the R1 register. In the step 5, the data stored in the R1 register is added by 4, and then the result is stored back to the R1 register. In the step 6, a memory write action is implemented to write the data that is stored in the R1 register into the memory address [2056].
The R1 register is for example an application programming register of the processor. Generally, the application programming registers are usually classified into three types, i.e. general purpose registers, segment registers and status registers. Examples of the general purpose registers include AX, BX, CX or DX registers. Examples of the segment registers include CS or DS registers.
In a case that no register-renaming operation is performed, the above steps need to be orderly implemented to execute the program. That is, the processor will execute the program having six steps according to the specified order as shown in FIG. 1A, so that it takes a relatively longer time period for implementing six steps.
By carefully analyzing the program of FIG. 1A, it is found that the steps 1˜3 and the steps 4˜6 utilize the same R1 register. Since data are written into the same position, the process of FIG. 1A is output-dependent and usually causes a write-after-write hazard. For avoiding the write-after-write hazard, the steps 1˜3 are implemented by the R1 register but the steps 4˜6 are implemented by another register (e.g. a R2 register). Under this circumstance, the steps 1˜3 and the steps 4˜6 could be simultaneously implemented. As shown in FIG. 1B, the steps 1˜3 and the steps 4˜6 are implemented by different execution units of the processor in parallel. In other words, it takes a relatively shorter time period for implementing three steps when the program is executed. Importantly, after the program is executed, the data stored in the R2 register need to be automatically written back to the R1 register. The process of using another register to replace the register of the source code is also referred as a register-renaming technology. Generally, the result of the register-renaming technology is stored in a register renaming table.
Generally, in a case that exception or branch misprediction occurs, some registers have been renamed and it fails to recover the contents of the register renaming table before occurrence of the exception or the branch misprediction. Under the circumstance, the execution of the program has failure.
Before the program is executed, the program is successively decoded by a decoding unit of the processor, then identification codes (IDs) are successively assigned to respective destination registers of the source codes by a renaming unit of the processor, and the IDs in the register renaming table are updated. Moreover, all refreshed data are recorded in a renaming-history table. If exception or branch misprediction occurs, the register renaming table could recover the contents according to the renaming-history table.
FIG. 2 schematically illustrates a process of executing another program according to the prior art. In the step a, a memory read action is implemented to temporarily store the data of the memory address [1024] into the AX register. At this moment, the AX register is the destination register. In the step b, the data stored in the AX register is added by 2, and then the result is stored in the BX register. At this moment, the BX register is the destination register. In the step c, the data stored in the CX register is temporarily stored in the BX register. At this moment, the BX register is the destination register. In the step d, the data stored in the BX register is added by 5, and then the result is stored in the CX register. At this moment, the CX register is the destination register. In the step e, the data stored in the AX register is added by 3, and then the result is stored in the DX register. At this moment, the DX register is the destination register. In the step f, the data stored in the CX register is temporarily stored in the AX register. At this moment, the AX register is the destination register. In the step g, the data stored in the BX register is added by 4, and then the result is stored in the DX register. At this moment, the DX register is the destination register. In the step h, the data stored in the AX register is added by 5, and then the result is stored in the BX register. At this moment, the BX register is the destination register.
The processes of creating the register renaming table and the renaming-history table when the program as shown in FIG. 2 is executed will be illustrated with reference to FIGS. 3A˜3H.
As shown in FIG. 3A, since the AX register is the destination register in the step a, the AX register is renamed as ID1 (i.e. the rename identification code is 1) in the register renaming table. As can be seen in the first row of the renaming-history table, a new ID1 register is added. According to the usage state “1” indicated by the occupy bit field (OC), it is found that ID1 is still valid. Afterwards, the data corresponding to AX will be referred to the data corresponding to ID1. Since the designations of BX, CX and DX are “−” (see FIG. 3A), the data corresponding to BX, CX and DX will be directly referred to the data corresponding to application programming registers BX, CX and DX, respectively.
As shown in FIG. 3B, since the BX register is the destination register in the step b, the register renaming table is updated such that the AX register is renamed as ID1 and the BX register is renamed as ID2 (i.e. the rename identification code is 2). As can be seen in the second row of the renaming-history table, a new ID2 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID2 is still valid.
As shown in FIG. 3C, since the BX register is the destination register in the step c, the register renaming table is updated such that the AX register is renamed as ID1 and the BX register is renamed as ID3 (i.e. the rename identification code is 3). As can be seen in the third row of the renaming-history table, a new ID3 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID3 is still valid.
As shown in FIG. 3D, since the CX register is the destination register in the step d, the register renaming table is updated such that the AX register is renamed as ID1, the BX register is renamed as ID3 and the CX register is renamed as ID4 (i.e. the rename identification code is 4). As can be seen in the fourth row of the renaming-history table, a new ID4 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID4 is still valid.
As shown in FIG. 3E, since the DX register is the destination register in the step e, the register renaming table is updated such that the AX register is renamed as ID1, the BX register is renamed as ID3, the CX register is renamed as ID4 and the DX register is renamed as ID5 (i.e. the rename identification code is 5). As can be seen in the fifth row of the renaming-history table, a new ID5 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID5 is still valid.
As shown in FIG. 3F, since the AX register is the destination register in the step e, the register renaming table is updated such that the AX register is renamed as ID6 (i.e. the rename identification code is 6), the BX register is renamed as ID3, the CX register is renamed as ID4 and the DX register is renamed as ID5. As can be seen in the sixth row of the renaming-history table, a new ID6 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID6 is still valid.
As shown in FIG. 3G, since the DX register is the destination register in the step g, the register renaming table is updated such that the AX register is renamed as ID6, the BX register is renamed as ID3, the CX register is renamed as ID4 and the DX register is renamed as ID7 (i.e. the rename identification code is 7). As can be seen in the seventh row of the renaming-history table, a new ID7 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID7 is still valid.
As shown in FIG. 3H, since the BX register is the destination register in the step h, the register renaming table is updated such that the AX register is renamed as ID6, the BX register is renamed as ID8 (i.e. the rename identification code is 8), the CX register is renamed as ID4 and the DX register is renamed as ID7. As can be seen in the eighth row of the renaming-history table, a new ID8 register is added. According to the usage state “1” indicated by the occupy bit field, it is found that ID8 is still valid.
After the instructions have been executed by the execution units of the processor, the results will be written back to the registers, and the renaming-history table and the register renaming table will be updated. As shown in FIG. 3I, after the data stored in the ID3 register are written back to the BX register, the value of the occupy bit field corresponding to the ID3 register of the renaming-history table cleared to be “0”. The usage state “0” indicates that the data stored in the renamed ID3 register has been written back to the BX register. Meanwhile, as shown in FIG. 3J, the ID3 register listed in the renaming-history table should be deleted.
Similarly, as shown in FIG. 3K, after the data stored in the ID4 register are written back to the CX register, the value of the occupy bit field corresponding to the ID4 register of the renaming-history table is cleared to be “0”. The usage state “0” indicates that the data stored in the renamed ID4 register has been written back to the CX register. Meanwhile, as shown in FIG. 3L, the ID4 register listed in the renaming-history table and the register renaming table should be deleted. Afterwards, other registers could be renamed as ID3 or ID4 again.
In other words, during the writing-back process, the renamed registers that are listed in the renaming-history table and comply with the writing-back ID will be deleted. Generally, a content addressable memory could be used to meet this requirement, because the operating speed of the content addressable memory is very fast. The content addressable memory, however, still has some drawbacks. For example, the layout area of the circuit of the content addressable memory is too large. In addition, since many data are possibly written back at the same time, the process of inquiring and deleting the contents of the renaming-history table usually consumes much power.
In a case that exception or branch misprediction occurs, the renaming-history table and the register renaming table should recover the contents before occurrence of the exception or the branch misprediction. That is, the data generated after occurrence of the exception or the branch misprediction need to be flushed. In addition, the value of the occupy bit field needs to be cleared to be “0”. For preventing from erroneously executing the program, the register renaming table should recover the contents before occurrence of the exception or the branch misprediction.
FIG. 4 schematically illustrates a process of executing a program with a branch misprediction step. As shown in FIG. 4, the program includes nine steps a˜i. In comparison with the program of FIG. 2, the branch misprediction that is indicated by “cBranch” occurs in the step f of the program of FIG. 4. Like the descriptions in FIGS. 3A-3L, the data stored in the ID3 register and ID4 register are written back.
FIGS. 5A˜5C schematically illustrate a process of recovering the register renaming table and the renaming-history table if branch misprediction occurs when the program as shown in FIG. 4 is executed. As shown in FIG. 5A, the branch misprediction “cBranch” occurs when the program is executed by the processor. Under this circumstance, the data generated after occurrence of the branch misprediction “cBranch” need to be flushed. That is, as shown in FIG. 5B, the data listed in the sixth, seventh, eighth and ninth rows of the renaming-history table should be deleted. In addition, the values of the occupy bit fields corresponding to the ID6, ID7, ID8 and ID9 registers of the renaming-history table are cleared to be “0”. Next, as shown in FIG. 5C, the register renaming table recovers the contents before occurrence of the branch misprediction. That is, the register renaming table recovers the contents to be synchronous with the data of the fifth row. Afterwards, the new register renaming operations could be continuously performed and started with the ID6.
From the above discussion, the renamed registers that are listed in the renaming-history table and comply with the writing-back ID are deleted during the writing-back process. This writing-back maintenance operation is usually implemented by using a content addressable memory. Although the operating speed of the content addressable memory is very fast, the process of inquiring and deleting the contents of the renaming-history table usually consumes much power and the layout area of the circuit of the content addressable memory is too large. Moreover, as the size of the renaming-history table is increased, the frequency of comparing the renamed registers with the writing-back ID is increased. Under this circumstance, the performance of executing the program is deteriorated.